#include <vector>
#include <algorithm>
#include <iostream>


// 贪心算法-1: 0-1背包问题
// 使用贪心算法解决凑零钱问题

/**
 *! @brief 使用贪心算法实现凑零钱的问题
 * 
 * @param coins    升序排列的硬币面值数组
 * @param amount   需要凑整的总价值数
 * 
 * @return int     返回最小的硬币数量
 */
int coinChangeGreedy(std::vector<int> coins, int amount) {
    int i     = coins.size() - 1;
    int count = 0;

    // 从大面额开始计数
    while(amount > 0) {
        while (i > 0 && coins[i] > amount) {
            i--;
        }
        amount -= coins[i];
        count++;
    }

    return amount == 0 ? count : -1;
}




// 贪心算法-2: 分数背包问题
/**
 *! @brief  使用贪心算法实现分数容量问题
 * 
 * @param  weights    物品的重量列表
 * @param  values     物品的价值列表
 * @param  capacity   容器的重量容量
 * 
 * @return float      返回最优解总价值大小
 */

class Item {
public:
    int weight;
    int value;

    // 使用初始化列表
    // Item(int w, int v) : weight(w), value(v) {}
    Item(int w, int v) {
        this->weight = w;
        this->value  = v;
    }
};

float capacityGreedy(const std::vector<int>& weights, 
                    const std::vector<int>& values, 
                    int capacity) {
    std::vector<Item> items;
    for (int i = 0; i < weights.size(); i++) {
         //! 使用emplace_back代替push_back提高性能
        items.emplace_back(weights[i], values[i]);     
    }

    //!  注意比较函数的lambda表达式写法
    //   []中填写需要捕获的内容
    //   按照单位重量的价值从高到低排序
    std::sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return ((float)a.value/a.weight) > ((float)b.value/b.weight);
    });


    float res      = 0.0;
    for (const auto& item : items) {
        if (item.weight <= capacity) {
            res      += item.value;
            capacity -= item.weight;
        } else {
            res += (float) item.value / item.weight * capacity;
            break;
        }
    }

    return res;
}


int main(int argc, char *argv[]) {
    std::vector<int> weights = {10, 20,  30,  40,  50};
    std::vector<int> values  = {50, 120, 150, 210, 240};

    std::cout << coinChangeGreedy(weights, values, 60) << std::endl;

    return 0;
}